package algorithms.question.class05;

import common.util.MyUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定两个字符串s1和s2，问s2最少删除多少字符可以成为s1的子串？
 * 比如 s1 = "abcde"，s2 = "axbc"
 *
 * @author guichang
 * @date 2021/8/1
 */

@SuppressWarnings("all")
public class Code4_删字符的字串 {

    // 方法2：遍历s1的所有字串看看s2删除几个字符能变成。删除的编辑距离


    public static void main(String[] args) {
        MyUtil.print(subString1("abcde", "axbc"));
    }

    /**
     * 方法1：生成s2的全排列，按长度从大到小排序，用indexOf比较
     */
    public static int subString1(String s1, String s2) {
        if (s1 == null || s2 == null) {
            return -1;
        }
        List<String> list = new ArrayList<>();
        // s2的全排列
        process(s2.toCharArray(), 0, "", list);
        // 长度降序
        list.sort((a, b) -> b.length() - a.length());
        for (String sub : list) {
            if (s1.indexOf(sub) > -1) {
                MyUtil.print(sub);
                return s2.length() - sub.length();
            }
        }
        return -1;
    }

    /**
     * 递归获取所有子序列
     *
     * @param cs    字符串的char数组
     * @param index 当前来到了index位置
     * @param path  选择的路径
     * @param list  所有子序列列表
     */
    private static void process(char[] cs, int index, String path, List<String> list) {
        // 选择完了
        if (index == cs.length) {
            list.add(path);
            return;
        }
        // 选择index位置的字符
        process(cs, index + 1, path + cs[index], list);
        // 不选择index位置的字符
        process(cs, index + 1, path, list);
    }

}